/**
 * 
 */
package dp.passed;

import java.util.LinkedList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class MinimumCoinsChange {

	/**
	* You are given n types of coin denominations of values 
	* v(1) < v(2) < ... < v(n) (all integers). 
	* Assume v(1) = 1, so you can always make change for 
	* any amount of money C. Give an algorithm which makes 
	* change for an amount of money C with as few coins as possible. 
	 */

	/*
	// c[i]: minimum number of coins needed
	// c[i] = min(c[i-j]) + 1 if j is an available coin and i>=j
	// answer: c[money]
	// complexity: O(money*coins), O(money)
	 */
	public int minCoins(int money, int[] coins, List<Integer> usedCoins) {

		int[] minCoins = new int[money + 1];
		for (int cents = 1; cents <= money; cents++) {
			minCoins[cents] = cents;
			for (int i = 0; i < coins.length; i++) {
				if (coins[i] <= cents) {
					if (minCoins[cents - coins[i]] + 1 < minCoins[cents]) {
						minCoins[cents] = minCoins[cents - coins[i]] + 1;
					}
				}
			}
		}

		return minCoins[money];
	}

	/**
	 * 
	 */
	public MinimumCoinsChange() {
		// TODO Auto-generated constructor stub
	}

	/**
	给定6个数字，a1~a6，代表价值为 1~6 的硬币个数。Sum(a1~a6)<10000. 把他们分成两堆，两堆的价值一样。
	http://blog.csdn.net/bison2008/article/details/6951458
	 */

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MinimumCoinsChange mcc = new MinimumCoinsChange();
		int[] coins = { 1, 10, 25 };
		int[] moneys = { 1, 5, 10, 15, 20, 21, 25, 30 };
		List<Integer> usedCoins = new LinkedList<Integer>();
		for (int money : moneys) {
			System.out.printf("%d cnets has min %d coins\n", money,
					mcc.minCoins(money, coins, usedCoins));
		}
	}

}
